# grid = [[1,3,1],[1,5,1],[4,2,1]]
# grid=[[1,2,3],[4,5,6]]
#超时用例
grid=[[7,1,3,5,8,9,9,2,1,9,0,8,3,1,6,6,9,5],[9,5,9,4,0,4,8,8,9,5,7,3,6,6,6,9,1,6],[8,2,9,1,3,1,9,7,2,5,3,1,2,4,8,2,8,8],[6,7,9,8,4,8,3,0,4,0,9,6,6,0,0,5,1,4],[7,1,3,1,8,8,3,1,2,1,5,0,2,1,9,1,1,4],[9,5,4,3,5,6,1,3,6,4,9,7,0,8,0,3,9,9],[1,4,2,5,8,7,7,0,0,7,1,2,1,2,7,7,7,4],[3,9,7,9,5,8,9,5,6,9,8,8,0,1,4,2,8,2],[1,5,2,2,2,5,6,3,9,3,1,7,9,6,8,6,8,3],[5,7,8,3,8,8,3,9,9,8,1,9,2,5,4,7,7,7],[2,3,2,4,8,5,1,7,2,9,5,2,4,2,9,2,8,7],[0,1,6,1,1,0,0,6,5,4,3,4,3,7,9,6,1,9]]
def dg(grid,x,y,path,res):
    #出口条件
    if(x>=len(grid) or y>=len(grid[0])):
        return None
    if(x==len(grid)-1 and y==len(grid[0])-1):
        res.append(path[:])
        return None
    if x+1<len(grid):
        #表示下一个点在合理范围内
        path.append(grid[x+1][y])
        dg(grid,x+1,y,path,res)
        #回溯
        path.pop(len(path)-1)
    if y+1<len(grid[0]):
        path.append(grid[x][y+1])
        dg(grid,x,y+1,path,res)
        path.pop(len(path)-1)

def minPathSum(grid):
    #最终结果矩阵
    res=[]
    #路径矩阵
    path=[]
    dg(grid,0,0,path,res)
    print(res)
    min=0
    for i in res[0]:
        min+=i
    for i in range(1,len(res)):
        sum=0
        for j in res[i]:
            sum+=j
        if sum<min:
            min=sum
    print(min+grid[0][0])
# minPathSum(grid)

def minPathSum_1(grid):
    dp=[[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
    # print(dp)
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if i==0 or j==0:
                if i==0 and j==0:
                    dp[i][j]=grid[0][0]
                elif i==0 and j!=0:
                    dp[i][j]=dp[i][j-1]+grid[i][j]
                elif i!=0 and j==0:
                    dp[i][j]=dp[i-1][j]+grid[i][j]
                else:
                    pass
            else:
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
    return dp[len(grid)-1][len(grid[0])-1]

print(minPathSum_1(grid))